package com.shindo.structure.class01;

/**
 * 插入排序 O(n^2) - 以最差情况考虑
 * <p>
 * 这个算法的思想有点像整理扑克牌的思路：从左往右开始看，哪张牌小，就抽出来放到左边
 * <p>
 * 想让arr[0~0]上有序，这个范围只有一个数，当然是有序的
 * 想让arr[0~1]上有序，从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做
 * 想让arr[0~i]上有序，从arr[i]开始往前看，arr[i]这个数不停向左移动，直到左边的数字不再比自己大，停止移动。
 * 最后一步，想让arr[0 ~ N-1]上有序，arr[N-1]这个数不停向左移动，直到左边的数字不再比自己大，停止移动。
 */
public class Code03_InsertionSort {
    public static void insertionSort(int[] arr) {
        if (null == arr || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void printArr(int[] arr) {
        if (null == arr || arr.length < 1) {
            return;
        }
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] testArr = new int[]{6, 3, 1, 8, 4, 12, 2, 7, 5};
        printArr(testArr);
        insertionSort(testArr);
        printArr(testArr);
    }
}
